from collections import Counter
from typing import List


class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        # ---------- 计算正确答案 ----------
        correct = eval(s)

        # ---------- 计算所有可能的错误答案 ----------
        s = "+" + s

        # 状态：[之前所有项的和，当前项乘号左侧，当前项乘号右侧]
        dp1 = {(0, -1, -1)}
        for i in range(0, len(s), 2):
            sign = s[i]  # 符号
            num = int(s[i + 1])  # 数字
            dp2 = set()
            for last, left, right in dp1:
                # last + left * right
                if sign == "+":
                    # 后计算加号
                    if left == -1 and right == -1:
                        dp2.add((last, num, -1))
                    elif left == -1:
                        pass
                    elif right == -1:
                        dp2.add((last + left, num, -1))
                        dp2.add((last, left + num, -1))
                    else:
                        dp2.add((last, left, right + num))
                        dp2.add((last + left * right, num, -1))
                        dp2.add((last, left * right + num, -1))
                else:  # sign == "*"
                    if left == -1 and right == -1:
                        pass
                    elif left == -1:
                        pass
                    elif right == -1:
                        dp2.add((last, left, num))
                        dp2.add((last, left * num, -1))
                    else:
                        dp2.add((last, left * right, num))  # 乘号作为加号位置的参考系，只有一个情况
                        dp2.add((last, left, right * num))  # 乘号作为加号位置的参考系，只有一个情况
                        dp2.add((last, left * right * num, -1))  # 乘号作为加号位置的参考系，只有一个情况
            dp1 = dp2
            print(dp1)

        # 计算所有错误答案
        wrong = set()
        for last, left, right in dp1:
            if left == -1 and right == -1:
                pass
            elif left == -1:
                pass
            elif right == -1:
                wrong.add(last + left)
            else:
                wrong.add(last + left * right)

        print(correct, wrong)

        ans = 0
        other = Counter()
        for answer in answers:
            if answer == correct:
                ans += 5
            elif answer in wrong:
                ans += 2
            else:
                other[answer] += 1

        print('未匹配:', other)

        return ans


if __name__ == "__main__":
    print(Solution().scoreOfStudents(s="7+3*1*2", answers=[20, 13, 42]))  # 7
    print(Solution().scoreOfStudents(s="3+5*2", answers=[13, 0, 10, 13, 13, 16, 16]))  # 19
    print(Solution().scoreOfStudents(s="6+0*1", answers=[12, 9, 6, 4, 8, 6]))  # 10

    # 测试用例 27/274
    print(Solution().scoreOfStudents(s="1+2*3+4", answers=[13, 21, 11, 15]))  # 11

    # 测试用例 29/274  预期: 122
    print(Solution().scoreOfStudents(s="4+2*2+3*1+2",
                                     answers=[42, 17, 13, 66, 32, 547, 21, 90, 13, 33, 45, 66, 34, 21, 13, 13, 13, 46,
                                              21, 177, 18, 13, 18, 16, 16, 678, 13, 42, 66, 13, 18, 18, 777, 21, 924,
                                              13, 268, 13, 13, 13, 25, 62, 45, 33, 888, 779, 13, 206, 48, 13, 34, 17]))
